/**
 * 柱状图中最大的矩阵
 *
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 * 示例 1:
 * 输入：heights = [2,1,5,6,2,3]
 * 输出：10
 * 解释：最大的矩形为图中红色区域，面积为 10
 *
 * 示例 2：
 * 输入： heights = [2,4]
 * 输出： 4
 *
 * 提示：
 * 1 <= heights.length <=105
 * 0 <= heights[i] <= 104
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 首先这题我们的暴力解法, 可以是先固定一个数, 然后遍历这个数两边的数,
 * 直到有比他小的就可以不用遍历了, 然后这就是以这个为顶的最大矩阵面积, 但
 * 是这个时间复杂度是 O(n ^ 2), 是超过时间限制的, 所以我们要来优化他
 *
 * 这里我们就要用刀单调栈了, 首先单调栈是一个栈, 并且这个栈中的元素是不会
 * 出现降序的, 我们可以利用单调栈的这个性质, 来寻找一个高度的两个边界, 但我们
 * 在遍历数组的时候发现了这个数小于栈顶的元素的时候, 就说明我们已经找到了他的右边界
 * 接下来我们还需要得到他的左边界, 左边界在哪里呢? 他就在我们栈顶元素后面的一个数,
 * 但是在栈中这两个数看起来是很近, 但在原来的数组中就不一定很近了, 因为单调栈的原因
 * 我们栈中的两个元素中间的的数肯定是要大于第一个数, 并且不会小于第二个数的, 所以我
 * 们的这个栈顶的矩阵长度要的是这两个数中间的长度, 后面还有一个细节问题, 就是当我们
 * 变遍历结束后, 我们的栈中可能还会有元素, 这个时候我们就要继续进行处理, 处理这种
 * 情况的时候我们也要小心, 这种情况右边界是固定的, 也就是数组的右边界, 因为要想有
 * 元素没处理掉, 肯定是要数组最右边的数在栈顶的, 后面栈中的元素肯定是小于他的, 那么
 * 我们求的矩阵也就可以加上右边的边界, 当然左边的边界还是和上面一样的, 然后就是我们
 * 遍历到最后一个元素的时候, 说明这个我们数组中的最小元素了, 这个时候他的长就是数组长度了
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(n)
 */

public class Main {

    // 测试用例
    public static void main(String[] args) {
        Main test = new Main();
        test.largestRectangleArea(new int[]{4, 2, 0, 3, 2, 5});
    }

    // 全局变量
    int maxArea;
    List<int[]> list;
    int len;

    public int largestRectangleArea(int[] nums) {

        int n = nums.length;

        // 初始化
        maxArea = 0;
        list = new ArrayList<>();
        len = 0;


        // 这里一开始我觉得 0 会处理不掉, 就将 0 给 分界了
        // 后面也是不用特殊处理的
        int tmp = 0;

        // for (int i = 0; i < n; i++) {
        //     if (nums[i] == 0) {
        //         findMax(nums, tmp, i - 1);
        //         tmp = i + 1;
        //     }
        // }

        findMax(nums, tmp, n - 1);

        return maxArea;
    }


    private void findMax(int[] nums, int i, int j) {

//        // 0 分界的特殊处理
//        if (i > j) {
//            return;
//        }

        for (int k = i; k <= j; k++) {

            len = list.size();

            //  list 为空的时候直接入栈
            if (len == 0) {

                list.add(new int[]{nums[k], k});

            } else {

                // 不为空, 取出栈顶元素
                int[] arr = list.get(len - 1);

                int a = arr[0], b = arr[1];

                // 看下这个数是否符合单调栈的条件
                if (a <= nums[k]) {

                    // 符合直接入栈
                    list.add(new int[]{nums[k], k});

                } else {

                    // 不符合, 我们更新 maxArea

                    // 先出栈顶元素， 没关系， 因为我们已经在前面记录了栈顶元素
                    list.remove(len - 1);

                    int ret = 0;

                    // 注意这个时候要是栈为 空的话, 我们是取不到栈后面的边界的
                    if (!list.isEmpty()) {

                        // 不为空, 左边界要注意算
                        ret = a * (k - list.get(list.size() - 1)[1] - 1);
                    } else {

                        // 为空了， 就直接是, 我们的数组左边界
                        ret = a * (k - i);
                    }

                    // 更新 maxArea
                    maxArea = Math.max(ret, maxArea);

                    // 这里我们再处理下保持这个数下面一次还要用
                    k--;

                }
            }
        }

        // 栈中还有元素
        len = list.size();
        while (len > 1) {

            // 记录栈顶元素
            int[] arr = list.get(len - 1);
            int a = arr[0], b = arr[1];

            // 因为我们保持了栈中最后还会剩下一个元素， 所以直接用, 不会越界

            // 左边界一样, 右边界一直是数组的最右边
            int ret = a * (j - list.get(len - 2)[1]);

            // 更新 maxArea
            maxArea = Math.max(maxArea, ret);

            // 移除
            list.remove(len - 1);
            len--;

        }

        // 最后一个数的边界是整个数组长度
        maxArea = Math.max(maxArea, list.get(0)[0] * (j - i + 1));
        list.remove(0);
    }
}